package my.jwds.p307;

public class NumArray {
    public static void main(String[] args) {




        NumArray obj = new NumArray(new int[]{1,3,5});
        System.out.println(obj.sumRange(0,2));
        obj.update(1,2);
        System.out.println(obj.sumRange(0,2));
    }



    int []c;
    int []nums;
    public NumArray(int[] nums) {
        c = new int[nums.length+1];
        this.nums = nums;
        for (int i = 0; i < nums.length; i++) {
            add(i+1,nums[i]);
        }
    }

    public void update(int index, int val) {
        int diff = val - nums[index];
        nums[index] =val;
        add(index+1,diff);
    }

    public int sumRange(int left, int right) {
        return query(right+1) - query(left+1) + nums[left];
    }


    int query(int index){
        int sum = 0;
        while(index != 0){
            sum += c[index];
            index-=lowbit(index);
        }
        return sum;
    }

    void add(int index,int val){
        while(index < c.length){
            c[index] += val;
            index +=lowbit(index);
        }
    }


    int lowbit(int m){
        return m &(-m);
    }
}